/**
 * NOTE: 字典树(Trie=>(前缀树)): N 叉树(N>2); 解决字符串的问题, 只用来处理字符串的问题,
 * 查询的时间复杂度根查询的字符长度有关, 以字符为单位构成一个树的结构
 *
 */

/**
 * Trie 只能存储字符串, 一个字符串的集合;
 * 缺点: 浪费空间
 */
export class TrieNode {
  public isWord: boolean = false
  // 权重
  public value: number = 0

  // 多叉树保持子节点
  public next: Map<string, TrieNode>

  constructor(isWord: boolean = false) {
    this.isWord = isWord
    this.next = new Map()
  }
}

export class TrieTree {

  private root!: TrieNode
  private size: number = 0

  constructor() {
    this.root = new TrieNode()
  }

  /**
   * getSize
   */
  public getSize() {
    return this.size
  }

  /**
   * add: 添加一个单词, 将单词变为一个个字符添加到 trie 树中, 不包含权重
   */
  public add(word: string) {
    let cur = this.root
    for (let i = 0; i < word.length; i++) {
      let c = word.charAt(i)
      if (!cur.next.get(c)) {
        cur.next.set(c, new TrieNode())
      }
      cur = cur.next.get(c) as TrieNode
    }
    // 表示一个新的单词
    if (!cur.isWord) {
      cur.isWord = true
      this.size++
    }
  }

  /**
   * delete: 删除一个 word
   */
  public delete(word: string): boolean {
    let cur = this.root
    if (!this.contains(word)) {
      return false
    }
    for (let arr = word, i = 0; i < arr.length; i++) {
      let char = arr[i]
      cur = cur.next.get(char) as TrieNode
    }
    if (cur.next.size === 0) {
      this.root.next.delete(word.charAt(0))
      return true
    }
    cur.isWord = false
    cur.value = 0
    return true
  }

  /**
   * contains: 查询单词 word 是否在 Tried 中
   */
  public contains(word: string): boolean {
    let cur = this.root
    for (let arr = word, i = 0; i < arr.length; i++) {
      let char = word.charAt(i)
      if (!cur.next.get(char)) {
        return false
      }
      cur = cur.next.get(char) as TrieNode
    }
    return cur.isWord
  }

  /**
   * isPrefix: 查询是否在 Trie 中有单词以 prefix 为前缀
   */
  public startsWith(prefix: string) {
    let cur = this.root
    for (let arr = prefix, i = 0; i < arr.length; i++) {
      let char = prefix.charAt(i)
      if (!cur.next.get(char)) {
        return false
      }
      cur = cur.next.get(char) as TrieNode
    }
    return true
  }

  /**
   * search: 简单的模糊搜索: 比如支持 点号 "." 的正则
   * eg: word => he..o
   */
  public search(word: string) {
    return this.match(this.root, word, 0)
  }

  /**
   * sumPrefix: 包含该前缀的总和
   */
  public sumPrefix(prefix: string): number {
    let cur = this.root

    for (let arr = prefix, i = 0; i < arr.length; i++) {
      let char = prefix.charAt(i)
      if (!cur.next.get(char)) {
        return 0
      }
      cur = cur.next.get(char) as TrieNode
    }
    return this.sum(cur)
  }

  /**
   * insert: 插入一个值, 并且支持权重 value
   */
  public insert(word: string, value: number) {
    let cur = this.root
    for (let i = 0; i < word.length; i++) {
      let c = word.charAt(i)
      if (!cur.next.get(c)) {
        cur.next.set(c, new TrieNode())
      }
      cur = cur.next.get(c) as TrieNode
    }
    // 表示一个新的单词
    if (!cur.isWord) {
      cur.isWord = true
      cur.value = value
      this.size++
    }
  }

  private sum(node: TrieNode): number {
    let ret = node.value
    // 需要递归到叶子节点, 这里不需要判断叶子节点, 因为非叶子节点的 value 为 0; 可以直接相加
    for (const item of node.next.keys()) {
      ret += this.sum(node.next.get(item) as TrieNode)
    }
    return ret
  }

  private match(node: TrieNode, word: string, index: number): boolean {
    if (index === word.length) {
      return node.isWord
    }

    let c = word.charAt(index)

    if (c !== '.') {
      if (!node.next.get(c)) {
        return false
      }
      return this.match(node.next.get(c) as TrieNode, word, index + 1)
    }
    for (const nextChar of node.next.keys()) {
      // 不需要判断是否相等, . 为任意字符
      if (this.match(node.next.get(nextChar) as TrieNode, word, index + 1)) {
        return true
      }
    }
    return false
  }
}

// 更多的字符串的问题, 查询问题: KMP, Boyer-Moore, Rabin-Karp
